home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12576 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB

  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Question on 'bubble sort'
  5. Date: 1 Apr 1996 10:53:11 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4jp8mnINNmq0@keats.ugrad.cs.ubc.ca>
  8. References: <4jieso$juc@lantana.singnet.com.sg> <828206958snz@genesis.demon.co.uk> <4jmv0d$t2p@news1.mnsinc.com>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4jmv0d$t2p@news1.mnsinc.com>,
  12. Szu-Wen Huang <huang@mnsinc.com> wrote:
  13.  >Lawrence Kirby (fred@genesis.demon.co.uk) wrote:
  14.  >: In article <4jieso$juc@lantana.singnet.com.sg>
  15.  >:            s8700055@singnet.com.sg "XY Xie" writes:
  16.  >
  17.  >: >I came across this sorting algorithm called 'bubble sort' in a book.
  18.  >
  19.  >: If the book doesn't explain why there is never a good reason to use bubble
  20.  >: sort then I suggest you get another book.
  21.  >
  22.  >Sure there is.  If I had 5 minutes to code something that will sort
  23.  >10 numbers, bubblesort comes in real handy.  If you've ever joined
  24.  >a programming contest you'll know what I mean.
  25.  
  26.  
  27. It's also good for sorting a fixed number of points. Say I had to sort the
  28. three vertices of a triangle in order of increasing y coordinate. What you do
  29. is just compare the first two points, possibly swap, then the last two points,
  30. possibly swap and then compare the first two points again, possibly swapping.
  31.  
  32. This is just a special case of the bubble sort and I have used it in polygon
  33. drawing code.
  34.  
  35. The asymptotic complexity of algorithms matters little on any data set whose
  36. size is fixed in advance, especially when the size is small. The precise size
  37. at which the algorithm with better complexity surpasses the worse algorithm in
  38. performance depends on the constants introduced by the implementation.
  39. -- 
  40.  
  41.